package binarytree

// 对称性的判断的核心要点是：左子树的左节点和右子树的右节点要成对比较，左子树的右节点和右子树的左节点也要成对比较。

func IsSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return isMirror(root.Left, root.Right)
}
func isMirror(left, right *TreeNode) bool {
	// If both nodes are nil, they are symmetric
	// If one is nil and the other is not, they are not symmetric
	// If both nodes are not nil, check their values and recursively check their children
	if left == nil && right == nil {
		return true
	}
	if left == nil || right == nil {
		return false
	}
	if left.Val != right.Val {
		return false
	}
	// Recursively check the left subtree of the left node with the right subtree of the right node
	// and the right subtree of the left node with the left subtree of the right node
	// 因为我们要检查的是对称性，所以需要比较左子树的左子节点和右子树的右子节点，
	// 以及左子树的右子节点和右子树的左子节点。
	return isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)
}

// IsSymmetric checks if a binary tree is symmetric around its center.
// It returns true if the tree is symmetric, otherwise false.
// The function uses a helper function `isMirror` to compare the left and right subtrees.
// The `isMirror` function checks if two trees are mirror images of each other.
// It recursively compares the left subtree of one tree with the right subtree of the other tree and vice versa.
// If both subtrees are nil, they are symmetric. If one is nil and the other is not, they are not symmetric.
// If the values of the nodes are different, they are not symmetric.
// The function continues to check the left and right children of both subtrees until it either finds a mismatch or confirms symmetry.

// 使用迭代的方法来检查二叉树是否对称
func IsSymmetricIterative(root *TreeNode) bool {
	if root == nil {
		return true
	}
	queue := []*TreeNode{root.Left, root.Right}
	// 核心思路是：
	// 使用队列进行广度优先搜索，逐层比较左右子树的节点
	// 关键是入队列的时候要注意顺序，
	// 左子树的左节点和右子树的右节点要成对入队，
	// 左子树的右节点和右子树的左节点也要成对入队。
	for len(queue) > 0 {
		left := queue[0]
		right := queue[1]
		queue = queue[2:]

		if left == nil && right == nil {
			continue
		}
		if left == nil || right == nil || left.Val != right.Val {
			return false
		}

		queue = append(queue, left.Left, right.Right, left.Right, right.Left)
	}
	return true
}
